package com.redblacktree;

public class RedBlackTree<Key extends Comparable<Key>,Value>{
    private Node root;
    private int N;
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    //获取树中元素个数
    public int size(){
        return N;
    }
    /**
     * 判断父节点指向当前结点链接是否为红色
     */
    private boolean isRed(Node x){
        if(x == null){
            return false;
        }
        return x.color == RED;
    }
    /**
     * 左旋转
     * @param h 旋转的根结点
     */
    public Node rotateLeft(Node h){
        //获取结点的右子结点
        Node x = h.left;
        //让x的左子节点成为h的右子结点
        h.right = x.left;
        //让h成为x的左子结点
        x.right = h;
        //让h的color等同于x的color
        x.color = h.color;
        //h的color变为Red
        h.color = RED;
        //x成为父节点
        return x;
    }

    /**
     * 右旋转
     */
    public Node rotateRight(Node h){
        Node x = h.left;
        h.left = x.right;
        x.left = h;
        x.color = h.color;
        h.color = true;
        return x;
    }

    /**
     * 颜色反转
     */
    public void flipColors(Node h){
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }
    /**
     * 在整个树上完成插入操作
     */
    public void put(Key key,Value val){
        //从根结点开始插入
        root = put(root,key,val);
        //插入操作后保持根结点的颜色为黑色
        root.color = BLACK;

    }
    /**
     * 往指定的树上插入操作，并返回添加元素后的新树
     * @param h 表示插入结点的位置
     * @param key
     * @param val key和val共同组成插入的结点
     */
    private Node put(Node h,Key key,Value val){
        //每次插入节点的链接颜色默认都为红色
        if(h == null){
            N++;
            return new Node(key,val,null,null,RED);
        }
        //如果插入结点处已经存在结点，则与当前结点的值进行比较
        int com = key.compareTo((Key) h.key);
        if(com < 0 ){
            //插入结点的值比当前结点值要小
            //继续往左
            h.left = put(h.left,key,val);
        }else if(com > 0){
            h.right = put(h.right,key,val);
        }else {
            h.value = val;
        }
        //插入节点后对树进行调整
        //左旋，即红节点在右边，黑节点在左边的情况
        if(isRed(h.right) && !isRed(h.left)){
            h = rotateLeft(h);
        }
        //右旋，左边连续两个红节点，黑节点在右边
        if(isRed(h.left) && isRed(h.left.left)){
           h = rotateRight(h);
        }
        //颜色反转，左右两边都是红色节点
        if(isRed(h.left) && isRed(h.right)){
            flipColors(h);
        }
        return h;
    }

    //根据key从树种找到对应的位置，基于二叉树的查找
    public Value get(Key key){
        return get(root,key);
    }
    //从指定的树x中查找key的位置
    private Value get(Node x, Key key){
        if(x == null){
            return null;
        }
        int com = key.compareTo((Key) x.key);
        if(com < 0){
            return get(x.left,key);
        }else if(com > 0){
            return get(x.right,key);
        }else {
            return (Value) x.value;
        }
    }


}
